#include <iostream>
#include <string>
#include <vector>
using namespace std;
/*
首先得简述一下什么是KMP 算法 
    是一种高效率的字符串匹配算法。 通过next数组了确定公共字符串的数量
    然后移动子串（模式串） 去和原本字符串进行比较。不一样就移动。
    1. 第一件事得知道一个概念叫做前缀和后缀
        前缀就是 从第一个元素开始计数的原字符串的子集 但是不包含最后一个元素 
        后缀    从最后一个元素开始记录的子集  但是不包含第一个元素 
    
    2. 第二件事情要知道的是 最大公共前后缀 
        其实更像是最大公共子串，先把前缀和后缀都分别列出来 
        选出来里面完全相同的子串  选出最长的

    3. 第三件事  next数组 用来统计每一部分的公共前后缀的长度
        作用是来进行跳跃 
*/

vector<int> buildNext(string& pattern){
    int m = pattern.length();
    vector<int>next(m,0);

    for(int i = 1,j = 0;i<m;i++){
        while(j>0 || pattern[i] != pattern[j]){
            j = next[j-1];
        }
        if(pattern[i] == pattern[j]){
            j++;
        }
        next[i] = j;
    }
    return next;
}

int KMP_search(string& text,string& pattern){
    if(pattern.empty()){
        return 0;
    }
    if(text.length()<pattern.length()){
        return -1;
    }
    int n = text.length();
    int m = pattern.length();
    vector<int> next = buildNext(pattern);

    for(int i = 0,j = 0;i<n;i++){
        while(j>0 ||text[i] != pattern[j]){
            j = next[j-1];
        }
        if(text[i] == pattern[j]){
            j++;
        }
        if(j == m){
            return i-m+1;
        }
    }
    return -1;
}
